package com.ln.leetcode._143;


import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import java.util.stream.Collectors;

public class Solution {

    @Test
    public void test() {
//        testNode(new Integer[]{1, 2, 3, 4}, new Integer[]{1, 4, 2, 3});
//        testNode(new Integer[]{1, 2, 3, 4, 5}, new Integer[]{1, 5, 2, 4, 3});
        testNode(new Integer[]{1}, new Integer[]{1});
    }

    private void testNode(Integer[] originVals, Integer[] reorderVals) {
        ListNode node = joinNodes(originVals);
        AssertNode(node, originVals);
        reorderList(node);
        AssertNode(node, reorderVals);
    }

    private ListNode joinNodes(Integer... vals) {
        List<ListNode> collect = Arrays.stream(vals).map(ListNode::new).collect(Collectors.toList());
        for (int i = 0; i < collect.size() - 1; i++) {
            collect.get(i).next = collect.get(i + 1);
        }
        return collect.get(0);
    }

    private void AssertNode(ListNode head, Integer... expectVals) {
        ListNode pos = head;
        for (int i = 0; i < expectVals.length; i++) {
            Assert.assertEquals(expectVals[i], pos.val);
            pos = pos.next;
        }
    }


    /**
     * 解题
     * 1. 快慢指针确定中间与末尾节点
     * 2. 后半倒排
     * 3. 归并
     */
    public void reorderList(ListNode head) {

        // 中间的节点
        ListNode middle = findMillde(head);
        ListNode secondHalf = middle.next;
        // 切断链表
        middle.next = null;
        // 后半段倒排
        ListNode reverseStart = reverse(secondHalf);
        // 归并
        merger(head, reverseStart);
    }

    public void merger(ListNode start1, ListNode start2) {
        while (start1 != null && start2 != null) {
            ListNode start1Next = start1.next;
            ListNode start2Next = start2.next;
            // 拼接
            start1.next = start2;
            start2.next = start1Next;
            // 后移
            start1 = start1Next;
            start2 = start2Next;
        }
    }


    /**
     * 链表倒排，三指针倒排方法
     * <pre>
     *     [1] -> [2] -> [3] -> [4] -> null
     *      n1     n2     n3
     *
     *     [1] <- [2]    [3] -> [4] -> null
     *      n1     n2     n3
     *
     *     [1] <- [2]    [3] -> [4] -> null
     *             n1     n2     n3
     *
     *     [1] <- [2] <- [3]    [4] -> null
     *             n1     n2     n3
     *
     *     [1] <- [2] <- [3]    [4] -> null
     *                    n1     n2     n3
     *
     *     [1] <- [2] <- [3] <- [4]    null
     *                    n1     n2     n3
     *
     *
     * </pre>
     *
     * @param startNode
     * @return 返回倒序后的头结点
     */
    private ListNode reverse(ListNode startNode) {
        ListNode n1 = startNode;
        if(n1 == null) {
            return n1;
        }
        ListNode n2 = n1.next;
        if (n2 == null) {
            return n1;
        }
        ListNode n3 = n2.next;

        for (; ; ) {
            // n1 n2 调换
            if (n1.equals(startNode)) {
                n1.next = null;
            }
            n2.next = n1;

            // 终止循环条件
            if (n3 == null) {
                break;
            }

            // 后移
            n1 = n2;
            n2 = n3;
            n3 = n3.next;
        }

        return n2;
    }

    private ListNode findMillde(ListNode startNode) {
        ListNode slowNode = startNode;
        ListNode fastNode = startNode;

        while (fastNode.next != null && fastNode.next.next != null) {
            // 慢走一步
            slowNode = slowNode.next;
            // 快走两步
            fastNode = fastNode.next.next;
        }

        return slowNode;
    }

}
